package org.algorithm.biubiu.wheel_1.链表;

import org.algorithm.biubiu.wheel_1.common.ListNode;
import org.junit.Test;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author jiazhaoxin
 * @Date 2022/2/17
 * @Desc {https://leetcode-cn.com/problems/partition-list/}
 */
public class 分隔链表 {


    @Test
    public  void test(){
        Queue<ListNode> smal  = new LinkedList();
//        smal.

    }

    public ListNode partition(ListNode head, int x) {

        ListNode smallHead = new ListNode(-1);
        ListNode bigHead = new ListNode(-1);
        ListNode small = smallHead,big=bigHead;
        while(head!=null){
            if(head.val<x){
                small.next = head;
                small = small.next;
            }else{
                big.next = head;
                big = big.next;
            }
            head = head.next;
        }
        big.next = null;
        small.next = bigHead.next;
        return smallHead.next;
    }

    public ListNode partition2(ListNode head, int x) {

        Queue<ListNode> smal  = new LinkedList();
        Queue<ListNode> big  = new LinkedList();
        ListNode dummy = head;
        while(dummy!=null){
            if(dummy.val<x){
                smal.add(dummy);
            }else{
                big.add(dummy);
            }
            dummy = dummy.next;
        }
        ListNode result = new ListNode(-1);
        dummy = result;
        while(!smal.isEmpty()){
            ListNode poll =  smal.poll();
            poll.next=null;
            dummy.next =poll;
            dummy = dummy.next;
        }
        while(!big.isEmpty()){
            ListNode poll =  big.poll();
            poll.next=null;
            dummy.next = poll;
            dummy = dummy.next;
        }
        return result.next;

    }

}
